package com.zzw.hj70;

import java.util.Scanner;
import java.util.Stack;

/**
 * @Project: hw_java
 * @Description: 矩阵乘法计算量估算
 * @Author: zzw
 */

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            // 要计算的矩阵个数
            int n = scanner.nextInt();
            // 数组，存储每个矩阵的行数，列数
            int[][] arr = new int[n][2];
            for (int i = 0; i < n; i++) {
                arr[i][0] = scanner.nextInt();
                arr[i][1] = scanner.nextInt();
            }
            scanner.nextLine();
            // 计算法则
            String str = scanner.nextLine();
            System.out.println(timesOfMatrixMultiplication(str, arr));
        }
    }

    /**
     * 思路如下：
     * 计算字母与‘A'的差值，得到矩阵的运算顺序并压入栈
     * 访问规则是遇到字母入栈，遇到右括号出栈两个，比如遇到第一个右括号出栈的是C，B，则用x和y接收C,B的运算顺序(x和y为对应数组的行坐标),然后计算出此次矩阵运算的乘法计算量
     * 计算除后，将结果的列值赋值给后出栈的矩阵的列值，将后出栈的矩阵的运算顺序再次入栈
     * 以此循环累加，得到总的乘法计算量
     *
     * <p>
     * 对于m×n的矩阵A和n×p的矩阵B，基本计算量为m×n×p次乘法操作。这是因为对于A的每一行和B的每一列，都需要进行n次乘法运算来计算结果矩阵C的一个元素。
     * </p>
     *
     * @param str
     * @param arr
     * @return
     */
    private static int timesOfMatrixMultiplication(String str, int[][] arr) {
        // 需要进行的乘法次数
        int total = 0;
        Stack<Integer> stack = new Stack<>();
        for (char c : str.toCharArray()) {
            if (c != '(') {
                if (c == ')') {
                    int x = stack.pop();
                    int y = stack.pop();
                    // 对于m×n的矩阵A和n×p的矩阵B，基本计算量为m×n×p次乘法操作。这是因为对于A的每一行和B的每一列，都需要进行n次乘法运算来计算结果矩阵C的一个元素。
                    total += arr[y][0] * arr[y][1] * arr[x][1];
                    arr[y][1] = arr[x][1];
                    stack.add(y);
                } else {
                    // 将矩阵的运算顺序入栈
                    int i = c - 'A';
                    stack.add(i);
                }
            }
        }

        return total;
    }
}
